package com.dmall.directed.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 拓扑排序
 * @author: xiao1.wang
 * @date: 2022/9/4 15:35
 */
public class TopoSort {

    private Graph G;
    private ArrayList<Integer> res;
    private boolean hasCycle = false;

    public TopoSort(Graph G) {
        if (!G.isDirected()) {
            throw new IllegalArgumentException("TopoSort only works in directed graph.");
        }

        this.G = G;
        this.res = new ArrayList<>();

        int[] indegrees = new int[G.V()];
        Queue<Integer> queue = new LinkedList<>();
        for (int v = 0; v < G.V(); v++) {
            indegrees[v] = G.indegree(v);
            if (indegrees[v] == 0) {
                queue.add(v);
            }
        }

        while (!queue.isEmpty()) {
            int v = queue.remove();
            res.add(v);
            for (int w : G.adj(v)) {
                indegrees[w] --;
                if (indegrees[w] == 0) {
                    queue.add(w);
                }
            }
        }

        if (res.size() < G.V()) {
            hasCycle = true;
            res.clear();
        }
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public ArrayList<Integer> result() {
        return res;
    }

    public static void main(String[] args) {
        String filename = TopoSort.class.getClassLoader().getResource("com/dmall/directed/graph/ug.txt").getPath();
        Graph g = new Graph(filename, true);
        TopoSort topoSort = new TopoSort(g);
        System.out.println(topoSort.hasCycle());
        System.out.println(topoSort.result());

        String filename2 = TopoSort.class.getClassLoader().getResource("com/dmall/directed/graph/ug3.txt").getPath();
        Graph g2 = new Graph(filename2, true);
        TopoSort topoSort2 = new TopoSort(g2);
        System.out.println(topoSort2.hasCycle());
        System.out.println(topoSort2.result());

        String filename3 = TopoSort.class.getClassLoader().getResource("com/dmall/directed/graph/ug4.txt").getPath();
        Graph g3 = new Graph(filename3, true);
        TopoSort topoSort3 = new TopoSort(g3);
        System.out.println(topoSort3.hasCycle());
        System.out.println(topoSort3.result());
    }
}
